# include <bits/stdc++.h>
using namespace std;

inline int gn() { 
    register int k = 0, f = 1;
    register char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
    return k * f;
}

int c[2017][2017], n, m, k, t;

inline void init() { 
    for(int i = 1; i <= )
}

int C(int a, int b) { // Cmn
    if(c[a][b]) return c[a][b] %= k;
    else if(!a || a == b) return c[a][b] = 1;
    else return (c[a][b] = C(a - 1, b - 1) + C(a, b - 1)) %= k;
}

int main() { 
    freopen("problem.in", "r", stdin);
    freopen("problem.out", "w", stdout);
    t = gn(), k = gn();
    for(int i = 1; i <= t; i++) { 
        n = gn(), m = gn();
        int ans = 0;
        for(int a = 0; a <= n; a++) { 
            for(int b = 0; b <= min(a, m); b++) { 
                if(!(C(b, a) % k)) ans++;
            }
        }
        printf("%d\n", ans);
    }
}
